這題要找到單向鏈結串列中的循環節點,如果沒循環就回傳 null,這類型問題需要了解兩點:判斷有沒有循環、找到循環的起點。
分析:
鏈結串列的問題通常用快慢指針法解決,這個方法既有效率又不會用額外的空間,這題可以用兩個指針,一個慢指針(每次走一步)和一個快指針(每次走兩步)如果快指針和慢指針相遇,就表示鏈結串列存在循環。
步驟:
確認有沒有循環,讓快慢指針從鏈結串列的頭開始,慢指針每次移動一步,快指針每次移動兩步,如果相遇,說明有循環存在,不然快指針到 null(鏈結結束),說明沒循環。
找到循環的起點,當快慢指針相遇,把其中一個指針移回鏈結串列的頭,另一個指針保持在相遇點,兩個指針再以同速度(每次走一步)前進,直到它們再次遇到,相遇的節點就是循環的起點。
程式碼:
#Definition for singly-linked list.
#class ListNode(object):
#def init(self, x):
#self.val = x
#self.next = None
class Solution(object):
def detectCycle(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head:
return None
#初始化快慢指針
slow, fast = head, head
#判斷有沒有循環
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
# 找到循環起點
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow
return None
心得:
這題通過快慢指針法,解決判斷鏈結串列中是否有循環及找到循環的起點的問題,這種方法的空間複雜度是 O(1),是高效的解法,學這題的過程,讓我理解雙指針的運用,重點是在鏈結串列中找循環或特定節點,這類問題常出現在面試,了解背後的解題技巧對解決其他類似的問題也蠻有用的。